function getPrefixTable(str){
    const n = str.length
    const prefix = new Array(n)
    // 长度为 1 时不要比较了，直接设置 0
    prefix[0] = 0
    let len = 0 // 前一个字符串公共前后缀长度
    let i = 1 // 从长度为 2 开始比较
    while(i<n){
        if(str[i] === str[len]){
            // 公共前后缀变长
            len ++
            prefix[i] = len
            i++
        }else{
            // 查看是否和前面的匹配
            if(len > 0){
                len = prefix[len -1]
            }else{
                prefix[i] = len
                i++
            }
        }
    }
    // 移位
    prefix.unshift(-1)
    prefix.pop()
    return prefix
}

function kmpSearch(long,short){
    const prefix = getPrefixTable(short,new Array(short.length))
    // 用 i 记录 long，用 j 记录 short
    // m 记录 long，n 记录 short
    const n = short.length
    const m = long.length
    let i = 0,j=0
    while(i < m){
        // 匹配多个继续匹配
        if(j === (n-1) && long[i] === short[j]){
            j = prefix[j]
            console.log( 'begin at：'+(i-n+1)+'，end at：' + i)
        }

        // 匹配一个
        if(long[i] === short[j]){
            j++
            i++
        }else{
            j = prefix[j]
            if(j === -1){
                i++
                j++
            }
        }
    }
}

// let short = 'ababcabaa'
// console.log(getPrefixTable(short,new Array(short.length),short.length),short)
kmpSearch('aababcabaaabcababcabaa','ababcabaa')